贝尔曼方程

贝尔曼期望方程

贝尔曼方程（Bellman Equation）也被称作动态规划方程（Dynamic Programming Equation），由理查·贝尔曼（Richard Bellman）发现。

贝尔曼期望方程帮助我们计算在每个状态下采取每个可能行动的期望回报。它的基本思想是，当前状态的期望回报等于即时回报加上下一个状态的期望回报的折现值。

V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')]

其中：

$V^\pi(s)$ 是在策略 $\pi$ 下状态 $s$ 的价值。
$\pi(a|s)$ 是在状态 $s$ 下选择行动 $a$ 的策略概率。
$p(s', r | s, a)$ 是从状态 $s$ 采取行动 $a$ 转移到状态 $s'$ 并获得回报 $r$ 的概率。
$\gamma$ 是折现因子，用于减少未来回报的影响。
$V^\pi(s')$ 是状态 $s'$ 在策略 $\pi$ 下的价值。

图 3-4 是一个马尔可夫决策过程的简单例子，其中每个深色圆圈代表一个状态，一共有从 $S_1$ ～ $S_5$ 这 5 个状态。黑色实线箭头代表可以采取的动作，浅色小圆圈代表动作，需要注意，并非在每个状态都能采取所有动作，例如在状态 $S_1$ ，智能体只能采取 “保持 $S_1$ ” 和 “前往 $S_2$ ” 这两个动作，无法采取其他动作。

每个浅色小圆圈旁的数字代表在某个状态下采取某个动作能获得的奖励。虚线箭头代表采取动作后可能转移到的状态，箭头边上的数字代表转移概率，如果没有数字则表示转移概率为 1。例如，在 $S_2$ 下，如果采取动作 “前往 $S_3$ ”，就能得到奖励-2，并且转移到 $S_3$ ；在 $S_4$ 下，如果采取“概率前往”，就能得到奖励 1，并且会分别以概率 0.2, 0.4, 0.4 转移到 $S_2$ , $S_3$ 或 $S_4$ 。

接下来我们编写代码来表示图 3-4 中的马尔可夫决策过程，并定义两个策略。第一个策略是一个完全随机策略，即在每个状态下，智能体会以同样的概率选取它可能采取的动作。例如，在 $S_1$ 下，智能体会以 0.5 和 0.5 的概率选取动作 “保持 $S_1$ ” 和 “前往 $S_2$ ”。第二个策略是一个提前设定的一个策略。

S = ["s1", "s2", "s3", "s4", "s5"]  # 状态集合
A = ["保持s1", "前往s1", "前往s2", "前往s3", "前往s4", "前往s5", "概率前往"]  # 动作集合
# 状态转移函数
P = {
    "s1-保持s1": 1.0,
    "s1-前往s2": 1.0,
    "s2-前往s1": 1.0,
    "s2-前往s3": 1.0,
    "s3-前往s4": 1.0,
    "s3-前往s5": 1.0,
    "s4-前往s5": 1.0,
    "s4-概率前往-s2": 0.2,
    "s4-概率前往-s3": 0.4,
    "s4-概率前往-s4": 0.4,
}
# 奖励函数
R = {
    "s1-保持s1": -1,
    "s1-前往s2": 0,
    "s2-前往s1": -1,
    "s2-前往s3": -2,
    "s3-前往s4": -2,
    "s3-前往s5": 0,
    "s4-前往s5": 10,
    "s4-概率前往": 1,
}
gamma = 0.5  # 折扣因子
MDP = (S, A, P, R, gamma)

# 策略1,随机策略
Pi_1 = {
    "s1-保持s1": 0.5,
    "s1-前往s2": 0.5,
    "s2-前往s1": 0.5,
    "s2-前往s3": 0.5,
    "s3-前往s4": 0.5,
    "s3-前往s5": 0.5,
    "s4-前往s5": 0.5,
    "s4-概率前往": 0.5,
}
# 策略2
Pi_2 = {
    "s1-保持s1": 0.6,
    "s1-前往s2": 0.4,
    "s2-前往s1": 0.3,
    "s2-前往s3": 0.7,
    "s3-前往s4": 0.5,
    "s3-前往s5": 0.5,
    "s4-前往s5": 0.1,
    "s4-概率前往": 0.9,
}


# 把输入的两个字符串通过“-”连接,便于使用上述定义的P、R变量
def join(str1, str2):
    return str1 + '-' + str2

接下来我们想要计算该 MDP（马尔可夫决策过程）下一个策略的状态价值函数。

我们现在能用的方法是计算马尔可夫奖励过程（MRP）的解析解。这就让我们想到一个问题：能不能把一个马尔可夫决策过程（MDP）和一个策略转换成一个简单的MRP？答案是可以的。方法是把策略中的动作选择简化掉，这样我们就得到了一个没有动作选择的MRP。

具体来说，对于某一个状态，我们根据策略所有动作的概率进行加权，得到的奖励和就可以认为是一个 MRP 在该状态下的奖励，即：

r'(s) = \sum_{a \in A} \pi(a|s) r(s, a)

同理，我们计算采取动作的概率与使 $S$ 转移到 $S'$ 的概率的乘积，再将这些乘积相加，其和就是一个 MRP 的状态从 $S$ 转移至 $S'$ 的概率：

P'(s'|s) = \sum_{a \in A} \pi(a|s) P(s'|s, a)

于是，我们构建得到了一个 MRP: $(S,P',r',\gamma)$ 。根据价值函数的定义可以发现，转化前的 MDP 的状态价值函数和转化后的 MRP 的价值函数是一样的。于是我们可以用 MRP 中计算价值函数的解析解来计算这个 MDP 中该策略的状态价值函数。

我们接下来就编写代码来实现该方法，计算用随机策略（也就是代码中的Pi_1）时的状态价值函数。为了简单起见，我们直接给出转化后的 MRP 的状态转移矩阵和奖励函数。

gamma = 0.5
# 转化后的MRP的状态转移矩阵
P_from_mdp_to_mrp = [
    [0.5, 0.5, 0.0, 0.0, 0.0],
    [0.5, 0.0, 0.5, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.5, 0.5],
    [0.0, 0.1, 0.2, 0.2, 0.5],
    [0.0, 0.0, 0.0, 0.0, 1.0],
]
P_from_mdp_to_mrp = np.array(P_from_mdp_to_mrp)
R_from_mdp_to_mrp = [-0.5, -1.5, -1.0, 5.5, 0]

V = compute(P_from_mdp_to_mrp, R_from_mdp_to_mrp, gamma, 5)
print("MDP中每个状态价值分别为\n", V)

MDP中每个状态价值分别为
 [[-1.22555411]
 [-1.67666232]
 [ 0.51890482]
 [ 6.0756193 ]
 [ 0.        ]]

知道了状态价值函数 $V^\pi(s)$ 后，我们可以计算动作价值函数 $Q^\pi(s,a)$ 。例如（ $S_4$ ，概率前往）的动作价值为 2.152，根据以下公式可以计算得到：

这个 MRP 解析解的方法在状态动作集合比较大的时候不是很适用，那有没有其他的方法呢？可以使用动态规划算法来计算得到价值函数

\begin{aligned} Q^\pi(s,a) &= r(s,a) + \gamma \sum_{s'} p(s'|s,a) V^\pi(s')2.152 \\ Q^\pi(s,a) &= 1 + 0.5 \times (0.2 \times (-1.68) + 0.4 \times 0.52 + 0.4 \times 6.08) = 2.152 \end{aligned}

贝尔曼最优方程

数学上，它可以表示为：

V^*(s) = \max_a \sum_{s', r} p(s', r | s, a) [r + \gamma V^*(s')]

其中：

$V^*(s)$ 是状态 $s$ 在最优策略下的价值。
$p(s', r | s, a)$ 是从状态 $s$ 采取行动 $a$ 转移到状态 $s'$ 并获得回报 $r$ 的概率。
$\gamma$ 是折现因子，用于减少未来回报的影响。
$V^\pi(s')$ 是状态 $s'$ 在策略 $\pi$ 下的价值。

贝尔曼期望方程​

贝尔曼最优方程​

贝尔曼期望方程

贝尔曼最优方程